/**
 * 
 */
package leetCode;

/**
 * @author zhong
 *
 */
public class MaximumSumofTwoNonOverlappingSubarrays {
	public int maxSumTwoNoOverlap(int[] A, int L, int M) {
		int n = A.length;
		int[][] sum = new int[n][n];
		for (int i = 0; i < sum.length; i++) {
			sum[i][i] = A[i];
			for (int j = i + 1; j < sum.length; j++) {
				sum[i][j] = sum[i][j - 1] + A[j];
			}
		}
		int res = 0;
		for (int i = 0; i < sum.length + 1 - L; i++) {
			for (int j = 0; j < sum.length + 1 - M; j++) {
				if (i + L - 1 < j || j + M - 1 < i) {
					res = Math.max(res, sum[i][i + L - 1] + sum[j][j + M - 1]);
				}
			}
		}
		return res;
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int[] A = { 0, 6, 5, 2, 2, 5, 1, 9, 4 };
		int L = 1, M = 2;
		System.out.println(new MaximumSumofTwoNonOverlappingSubarrays().maxSumTwoNoOverlap(A, L, M));
	}

}
